class Solution {
    /*
        思路：DFS（较复杂代码）
    */
    boolean ans = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        dfs(root,0,targetSum);
        return ans;
    }
    public void dfs(TreeNode root,int sum,int targetSum){
        // 这里无法判断叶子节点
        if( root==null ){
            return;
        }
        sum += root.val;
        // 需要在这里判断是否是叶子节点
        if( root.left==null && root.right==null && sum==targetSum ){
            ans = true;
        }
        dfs(root.left,sum,targetSum);
        dfs(root.right,sum,targetSum);
    }
}
class Solution {
    /*
        思路：DFS（简单、优雅的代码）
    */  
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if( root==null )
            return false;
        if( root.left==null && root.right==null )
            return root.val == targetSum;
        return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
    }
}
class Solution {
    /*
        思路：BFS
    */  
    public boolean hasPathSum(TreeNode root, int targetSum) {
        Queue<TreeNode> q = new LinkedList<>();
        // 存在root为null的情况
        if( root!=null )
            q.add(root);
        while( !q.isEmpty() ){
            TreeNode tot = q.poll();
            // tot为叶子节点
            if( tot.left==null && tot.right==null && tot.val==targetSum ){
                return true;
            }
            if( tot.left!=null ){
                tot.left.val += tot.val;
                q.add(tot.left);
            }
            if( tot.right!=null ){
                tot.right.val += tot.val;
                q.add(tot.right);
            }
        }
        return false;
    }
}